package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 前序中序构建而二叉树
 *
 * @author lixiaowen
 * @create 2019-12-10
 */
public class ConstructBinaryTreefromPreorderandInorderTraversal105 {


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length || preorder.length <= 0) {
            return null;
        }

        //加速查找
        Map<Integer, Integer> map = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; ++i) {
            //key: 元素
            //value: 元素中序的索引
            map.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length - 1, 0, map);
    }


    /**
     * 递归构建树
     * @param preorder
     * @param left preorder
     * @param right
     * @param ileft
     * @param map
     * @return
     */
    private TreeNode buildTree(int[] preorder, int left, int right,
                               int ileft, Map<Integer, Integer> map) {
        //递归终止条件
        if (left > right) return null;
        TreeNode root = new TreeNode(preorder[left]);
        //关键位置，递归的切分点: inorder: root index
        Integer index = map.get(root.val);
        //注意构建子树的时， 前序和中序的元素个数相同
        root.left = buildTree(preorder, left + 1, left + (index - ileft), ileft, map);
        //递归构建右子树
        root.right = buildTree(preorder, left + (index - ileft) + 1, right, index + 1, map);
        return root;
    }
}
